﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Numerics;
using System.Text;
using System.Threading.Tasks;

namespace MagicSoundPro
{
    public class FourierTransform
    {
        //public Complex[] FFT(float[] data)
        //{
        //    int n = data.Length;
        //    var result = new Complex[n];

        //    for (int i = 0; i < n; i++)
        //    {
        //        result[i] = new Complex(data[i], 0);
        //    }

        //    FFT(result, false);

        //    return result;
        //}

        //public float[] IFFT(Complex[] data)
        //{
        //    int n = data.Length;
        //    var result = new Complex[n];

        //    for (int i = 0; i < n; i++)
        //    {
        //        result[i] = Complex.Conjugate(data[i]);
        //    }

        //    FFT(result, true);

        //    var timeData = new float[n];

        //    for (int i = 0; i < n; i++)
        //    {
        //        timeData[i] = (float)result[i].Real / n;
        //    }

        //    return timeData;
        //}

        //private void FFT(Complex[] data, bool inverse)
        //{
        //    int n = data.Length;

        //    if (n == 1)
        //    {
        //        return;
        //    }

        //    var even = new Complex[n / 2];
        //    var odd = new Complex[n / 2];

        //    for (int i = 0; i < n / 2; i++)
        //    {
        //        even[i] = data[2 * i];
        //        odd[i] = data[2 * i + 1];
        //    }

        //    FFT(even, inverse);
        //    FFT(odd, inverse);

        //    double angle = 2 * Math.PI / n * (inverse ? -1 : 1);

        //    for (int i = 0; i < n / 2; i++)
        //    {
        //        var t = Complex.FromPolarCoordinates(1, angle * i) * odd[i];
        //        data[i] = even[i] + t;
        //        data[i + n / 2] = even[i] - t;
        //    }
        //}

        public enum Direction
        {
            Forward, Backward
        }

        public static void FFT(Complex[] x, FourierTransform.Direction direction)
        {
            int n = x.Length;
            if (n == 1)
            {
                return;
            }

            Complex[] even = new Complex[n / 2];
            Complex[] odd = new Complex[n / 2];
            for (int i = 0; i < n / 2; i++)
            {
                even[i] = x[2 * i];
                odd[i] = x[2 * i + 1];
            }

            FFT(even, direction);
            FFT(odd, direction);

            double angle = 2 * Math.PI / n * (direction == FourierTransform.Direction.Forward ? -1 : 1);
            Complex w = new Complex(1, 0);
            Complex wn = new Complex(Math.Cos(angle), Math.Sin(angle));
            for (int i = 0; i < n / 2; i++)
            {
                x[i] = even[i] + w * odd[i];
                x[i + n / 2] = even[i] - w * odd[i];
                w *= wn;
            }
        }

        public static void IFFT(Complex[] x)
        {
            int n = x.Length;
            for (int i = 0; i < n; i++)
            {
                x[i] = Complex.Conjugate(x[i]);
            }

            FFT(x, FourierTransform.Direction.Forward);

            for (int i = 0; i < n; i++)
            {
                x[i] = Complex.Conjugate(x[i]) / n;
            }
        }

    }
}